package Top200;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-21 17:21
 * 回溯
 * 路径：已选择的列表
 * 选择列表：candidates[i]是否需要
 * 终止条件：刚好target满足
 */
public class combinationSum39 {
    List<List<Integer>> res=new LinkedList<>();
    void backtrack(int[] candidates,int index,int target,LinkedList<Integer> path){
        if (target<0||index>=candidates.length)return;
        if (target==0) {
            res.add(new LinkedList<>(path));
            return;
        }
        path.addLast(candidates[index]);
        backtrack(candidates,index,target-candidates[index],path);
        path.pollLast();

        backtrack(candidates,index+1,target,path);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates,0,target,new LinkedList<>());
        return res;
    }
}
